//
// Created by ASUS on 2023/9/20.
//

/*
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
示例 1：

输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
示例 2：

输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。
示例 3：

输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。


提示：

1 <= n <= 2 * 109
 */

#include <bits/stdc++.h>
using namespace std;

int countSpecialNumbers(int n) {
	auto s = to_string(n);
	int m = s.length(), memo[m][1 << 10];
	memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
	//i当前数位，mask选过的数字集合，isLimit是否收到n的约束，isNum表示i前面数位是否填了数字
	function<int(int, int, bool, bool)> f = [&](int i, int mask, bool is_limit, bool is_num) -> int {
		if (i == m)
			return is_num; // is_num 为 true 表示得到了一个合法数字
		if (!is_limit && is_num && memo[i][mask] != -1)
			return memo[i][mask];

		int res = 0;
		if (!is_num) // 可以跳过当前数位
			res = f(i + 1, mask, false, false);//第i位没有填数字，第i+1位也可以不填

		int up = is_limit ? s[i] - '0' : 9; // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
		for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d，前面没填数字，只能从1开始
			if ((mask >> d & 1) == 0) // d 不在 mask 中
				res += f(i + 1, mask | (1 << d), is_limit && d == up, true);
		if (!is_limit && is_num)
			memo[i][mask] = res;
		return res;
	};
	return f(0, 0, true, false);
}

int main(){
	cout<<countSpecialNumbers(135)<<endl;
	return 0;
}

/*
 * 时间复杂度：O(mD2^D)，其中 m 为 s 的长度，即 O(log n)；D=10。由于每个状态只会计算一次，因此动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。
 * 本题状态个数为 O(m2^D)，单个状态的计算时间为 O(D)，因此时间复杂度为 O(mD2^D)。
 *  空间复杂度：O(m2^D)
 */